/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                return true;
        }

        return false;





    }
};/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
            {
                ListNode* meet = fast;
                ListNode* cur = head;

                while (cur != meet)
                {
                    cur = cur->next;
                    meet = meet->next;
                }
                return cur;

            }



        }
        return nullptr;





    }
}; class Solution {
public:
    bool canPartition(vector<int>& num) {


        int sum = 0;

        for (int i = 0; i < num.size(); i++) {

            sum += num[i];
        }
        //cout<<sum<<endl;
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        vector<int>dp(target + 1, 0);
        // dp[0]=0;
        for (int i = 0; i < num.size(); i++) {
            for (int j = target; j >= num[i]; j--) {

                dp[j] = max(dp[j], dp[j - num[i]] + num[i]);
            }

        }

        if (dp[target] == target) return true;
        else return  false;

    }

};/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* newhead = new ListNode(-1);
        ListNode* tail = newhead;
        ListNode* cur1 = list1;
        ListNode* cur2 = list2;
        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                ListNode* newnode = new  ListNode(cur1->val);
                tail->next = newnode;
                tail = tail->next;
                cur1 = cur1->next;
            }
            else
            {

                ListNode* newnode = new  ListNode(cur2->val);
                tail->next = newnode;
                tail = tail->next;
                cur2 = cur2->next;

            }
        }
        while (cur1)
        {
            ListNode* newnode = new  ListNode(cur1->val);
            tail->next = newnode;
            tail = tail->next;
            cur1 = cur1->next;

        }
        while (cur2)
        {
            ListNode* newnode = new  ListNode(cur2->val);
            tail->next = newnode;
            tail = tail->next;
            cur2 = cur2->next;
        }
        tail->next = nullptr;
        return newhead->next;

    }
};/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr)
            return nullptr;
        ListNode* n1 = nullptr;
        ListNode* n2 = head;

        ListNode* n3 = head->next;
        while (n2) {

            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
                n3 = n3->next;
        }

        return n1;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //  l1 = reverseList(l1);
      //    l2 = reverseList(l2);
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* newhead = new ListNode(-1);
        ListNode* tail = newhead;
        int ret = 0;
        int t = 0;
        while (cur1 || cur2 || ret) {
            if (cur1) {
                ret += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2) {
                ret += cur2->val;
                cur2 = cur2->next;
            }

            ListNode* newnode = new ListNode(ret % 10);
            tail->next = newnode;
            tail = tail->next;
            ret /= 10;
        }
        return newhead->next;

        // return nullptr;   


    }
}; class Solution {
public:
    vector<int>result;
    void memrgesort(vector<int>& nums, int left, int right)
    {
        if (left >= right)return;
        int mid = (left + right) >> 1;
        memrgesort(nums, left, mid);
        memrgesort(nums, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            result[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid)
        {
            result[i++] = nums[cur1++];
        }
        while (cur2 <= right)
        {
            result[i++] = nums[cur2++];
        }
        for (int i = left; i <= right; i++)
        {
            nums[i] = result[i - left];
        }

    }



    vector<int> sortArray(vector<int>& nums) {
        result.resize(nums.size());
        memrgesort(nums, 0, nums.size() - 1);
        return nums;
    }
};/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head;
        ListNode* slow = head;
        int m = n + 1;
        while (m--)
        {
            if (fast == nullptr)return head->next;
            fast = fast->next;
        }
        while (fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;




    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ret = -1010;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ret;
    }
    int dfs(TreeNode* root)
    {
        if (root == nullptr)  return 0;


        int l = max(0, dfs(root->left));
        int r = max(0, dfs(root->right));

        ret = max(root->val + l + r, ret);

        return root->val + max(l, r);






    }
};